Various media besides text-format files, such as audio, images, natural language, and so forth, can be digitized on a computer and handled mathematically, whereby higher-level and wide-ranging data processing can be performed, such as editing/processing, accumulating, managing, transmitting, sharing, and so forth, of information. For example, image processing technology wherein a computer is used to subject an image to digital image processing such as alteration of shape, alteration of color, image quality enhancement, re-encoding, and so forth, is in widespread use. This image processing technology includes special effects, wherein objects such as unsightly utility poles are removed from a scenic photograph, morphing wherein a human face is smoothly changed into an animal face, and so forth. Image processing technology is also applied to various specialized fields in science and medicine and so forth, such as processing photograph pictures transmitted from a satellite, processing of diagnosis images read in with a CT scanner, and so forth.
For example, image processing technology wherein an image of a two-dimensional or three-dimensional physical object is generated and displayed is called “computer graphics (CG)”, and has received much attention. Generally, graphic systems of this type are configured of a geometric sub-system serving as the front end and a raster sub-system serving as the back end. Of these, the geometric sub-system handles an object as an assembly of a great number of minute polygons (normally triangles), with geometric calculations being performed regarding the vertices defining the polygons, such as coordinate transformation, clipping, light source calculation, and so forth.
Now, the coarseness of the mesh obtained by region division of the original object greatly affects the processing load and image quality. Region division of the original object into finer image regions proportionately increases the number of vertices to be processed, so the amount of processing increases. Also, larger-sized polygons result in the final product having a coarser image quality. Accordingly, processing such as merging the divided regions is performed to adjust the polygonal mesh into a suitable coarseness for the application using the CG, which is called mesh segmentation.
Mesh segmentation is a basic technique for growing raw data into a small number of perceivable increments called “segments”. Research of mesh segmentation began from an early period in computer image processing in the 1970's (e.g., see Non-Patent Document 1), and the field is still active. From the start, mesh segmentation has handled color images, moving images, distance images (known as depth image or range image), three-dimensional data, three-dimensional mesh, and so forth. Hierarchical segmentation can be realized by creating multiple polygonal meshes having differing coarseness in the mesh segmentation processing. Also, performing hierarchical mesh segmentation in a progressive, that is, a smooth manner, enables the range of applications using the images to be increased.
For example, a proposal has been made regarding mesh segmentation processing wherein hierarchical mesh decomposition is performed using fuzzy image clustering and image cutting (e.g., see Non-Patent Document 2).
Mesh segmentation is basically processed based on the degree of similarity between neighboring image regions. For example, color signals of an input picture is converted into a predetermined color space, initial picture division is performed wherein the input picture is divided into multiple regions in accordance with the positions of color pixels in the input picture within the color space, the divided regions are separated into multiple layers in accordance with the horizontal neighboring relation between the divided regions and the vertical inclusive relation thereof, neighbor regions within each layer are grouped to form region groups, of which the vertical inclusive relations are extracted so as to structure regions, the order of joining of the regions is determined based on the horizontal relation between the regions and the vertical inclusive relation between the region groups, feasibility of joining is determined for neighbor regions based on the determined joining order, and in the event that determination is made that the evaluated regions are regions which have substantially the same picture properties, the regions can be joined (e.g., see Non-Patent Document 1).
However, conventional mesh segmentation processing primarily performs region growing, or hierarchical/iterative/spectral clustering. That is to say, algebraic operations using arrays are repeatedly performed, so processing speed is slow. For example, processing around 400 polygons takes 1 to 57 seconds, so progressively generating multiple mesh segmentations with differing coarseness is difficult. Also, the system has no scalability, and increase in the number of polygons markedly increases the processing time. Accordingly calculation with common calculators such as personal computers (PC) is difficult, and is inapplicable to interactive applications where the real-time aspect is required. There are also problems such as original information relating to the original image is lost, a great number of parameter values must be adjusted, and so forth.    Patent Document 1 Japanese Unexamined Patent Application Publication No. 2001-43380    Non-Patent Document 1 A. Rosenfeld, “Picture processing by computer” (Academic press, 1969)    Non-Patent Document 2 Sagi Katz and Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cots” (In Proc. SIGGRAPH (2003). ACM Trans. on Graphics 22, 3 (2003), 382-391)